Assume that for every derandomization result for logspace algorithms, thereis a pseudorandom generator strong enough to nearly recover the derandomizationby iterating over all seeds and taking a majority vote. We prove under aprecise version of this assumption that $\mathbf{BPL} \subseteq \bigcap_{\alpha> 0} \mathbf{DSPACE}(\log^{1 + \alpha} n)$. We strengthen the theorem to an equivalence by considering twogeneralizations of the concept of a pseudorandom generator against logspace. Atargeted pseudorandom generator against logspace takes as input a short uniformrandom seed and a finite automaton; it outputs a long bitstring that looksrandom to that particular automaton. A simulation advice generator for logspacestretches a small uniform random seed into a long advice string; therequirement is that there is some logspace algorithm that, given a finiteautomaton and this advice string, simulates the automaton reading a longuniform random input. We prove that $\bigcap_{\alpha > 0}\mathbf{promise\mbox{-}BPSPACE}(\log^{1 + \alpha} n) = \bigcap_{\alpha > 0}\mathbf{promise\mbox{-}DSPACE}(\log^{1 + \alpha} n)$ if and only if for everytargeted pseudorandom generator against logspace, there is a simulation advicegenerator for logspace with similar parameters. Finally, we observe that in a certain uniform setting (namely, if we onlyworry about sequences of automata that can be generated in logspace), targetedpseudorandom generators against logspace can be transformed into simulationadvice generators with similar parameters.
展开▼
